package com.sheng.leetcode.year2022.month11.day28;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/11/28
 *<p>
 * 813. 最大平均值和的分组<p>
 *<p>
 * 给定数组nums和一个整数k。我们将给定的数组nums分成 最多k个相邻的非空子数组 。<p>
 * 分数 由每个子数组内的平均值的总和构成。<p>
 * 注意我们必须使用 nums 数组中的每一个数进行分组，并且分数不一定需要是整数。<p>
 * 返回我们所能得到的最大 分数 是多少。答案误差在10^-6内被视为是正确的。<p>
 *<p>
 * 示例 1:<p>
 * 输入: nums = [9,1,2,3,9], k = 3<p>
 * 输出: 20.00000<p>
 * 解释:<p>
 * nums 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20.<p>
 * 我们也可以把 nums 分成[9, 1], [2], [3, 9].<p>
 * 这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.<p>
 *<p>
 * 示例 2:<p>
 * 输入: nums = [1,2,3,4,5,6,7], k = 4<p>
 * 输出: 20.50000<p>
 *<p>
 * 提示:<p>
 * 1 <= nums.length <= 100<p>
 * 1 <= nums[i] <= 10^4<p>
 * 1 <= k <= nums.length<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/largest-sum-of-averages">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode0813 {

    @Test
    public void test01() {
//        int[] nums = {9,1,2,3,9}; int k = 3;
        int[] nums = {1,2,3,4,5,6,7}; int k = 4;
        System.out.println(new Solution().largestSumOfAverages(nums, k));
    }
}
class Solution {
    public double largestSumOfAverages(int[] nums, int k) {
        /**
         * 题目要求将数组 nums 分成 k 个相邻的非空数组，然后求出每个子数组的平均值之和
         * 思路：想办法获取划分区域内的最大值，最大值单独列出来
         */
        int length = nums.length;
        double[][] ans = new double[length + 1][k + 1];
        for (int i = 1; i <= length; i++) {
            ans[i][0] = -1e7;
            for (int j = 1; j <= k; j++) {
                for (int l = 0; l < i; l++) {
                    double sum = 0;
                    for (int m = l; m < i; m++) {
                        sum += nums[m];
                    }
                    ans[i][j] = Math.max(ans[i][j], ans[l][j - 1] + sum / (i - l));
                }
            }
        }
        return ans[length][k];
    }
}
